package Graph;

import java.util.Arrays;

public class MinTreeTest {
    public static void main(String[] args) {
        char [] dingdian={'A','B','C','D','E','F','G'};
        int vetex=dingdian.length;
        int [][]weight=new int[][]{
                {10000,5,7,10000,10000,10000,2}, // A
                {5,10000,10000,9,10000,10000,3}, // B
                {7,10000,10000,10000,8,10000,10000}, // C
                {10000,9,10000,10000,10000,4,10000}, // D
                {10000,10000,8,10000,10000,5,4}, // E
                {10000,10000,10000,4,5,10000,6}, // F
                {2,3,10000,10000,4,6,10000}}; // G

        Map map = new Map(vetex);
        MinTree minTree = new MinTree();
        minTree.Mygragh(map,dingdian,weight);
        minTree.show(map);
        minTree.prim(map,0);
    }
}
class MinTree{
    public void Mygragh(Map map,char[]dingdian,int[][]weitgh){
        for (int i = 0; i < map.vetexs; i++) {
            map.dingdian[i]=dingdian[i];
            for (int j = 0; j < map.vetexs; j++) {
                map.weitgh[i][j]=weitgh[i][j];
            }
        }
    }
    public void show(Map map){
        for (int [] arr:
                map.weitgh) {
            System.out.println(Arrays.toString(arr));
        }
    }
    public void prim(Map map,int v){
        //判断节点是否访问过
        int [] isvisited =new int[map.vetexs];
        isvisited[v]=1;
        int h1=0;
        int h2=0;
        int minWeight=10000;
        for (int i = 1; i <map.vetexs ; i++) {//保证有n-1条边
                for (int j = 0; j < map.vetexs; j++) {//结点j被访问过的结点
                    for (int k = 0; k < map.vetexs; k++) {//结点k没被范文过的
                        if (isvisited[j]==1 && isvisited[k]==0 && map.weitgh[j][k]<minWeight){
                            minWeight=map.weitgh[j][k];
                            h1=j;
                            h2=k;
                        }
                    }
                }
            System.out.println(map.dingdian[h1]+"-->"+map.dingdian[h2]+"权值为:"+minWeight);
            isvisited[h2]=1;
            minWeight=10000;
        }
    }
}
class Map{
    int vetexs;//节点个数
    char [] dingdian;//顶点
    int [][] weitgh;//权值
    public Map(int vetexs){
        this.vetexs = vetexs;
        dingdian = new char[vetexs];
        weitgh = new int[vetexs][vetexs];
    }

}


